1. Field of the Invention
The present invention relates to an apparatus for executing processing for compressing data length using an algebraic torus in the same manner as the public key cryptography or the like that bases its safety on difficulty of the discrete logarithm problem defined on a subgroup of a multiplicative group of finite fields.
2. Description of the Related Art
The discrete logarithm problem is a problem for calculating “x” that satisfies y=gx when yεG is given in a cyclic group G=<g>. As the cyclic group G, a multiplicative group of finite fields and an additive group (a Jacobian group) formed by rational points of an elliptic curve is used. These problems are used to form a public key cipher. As an algorithm for solving these problems, there are an algorithm that can be applied to the discrete logarithm problem defined on any cyclic group such as the Schank's algorithm and the Pollard' ρ method and an algorithm that can be applied to only the discrete logarithm problem defined on the multiplicative group of finite fields.
Because the order counting method is efficient, the public key cipher formed by using the discrete algorithm problem on the multiplicative group of finite fields is easily decoded. Therefore, to secure the same level of safety, the key length and the encrypted data length of the public key cipher formed by using the discrete logarithm problem on the multiplicative group of finite fields needs to be set larger than those of a public key cipher formed by using the discrete logarithm problem on the elliptic curve.
Therefore, the cipher compression technology for compressing a public key size and an encrypted data size in a public key cipher by using an algebraic torus is proposed (see, for example, K. Rubin and A. Silverberg “Torus-Based Cryptography”, CRYPTO 2003, Springer LNCS 2729, 349-365, 2003). The algebraic torus is defined as a subgroup of the multiplicative group of finite fields. The algebraic torus can compress an original representation. This makes it possible to solve the problem that the key length and the encrypted data length in the public key cipher formed by using the discrete logarithm problem on the multiplicative group of finite fields are large.
For example, elements of a finite field represented by Formula (1) are represented as (a1, a2, a3, a4, a5, a6) by using six components of a finite field represented by Formula (2). Note that ai (i=1 to 6) is an element of the finite field of Formula (2). On the other hand, a sixth order torus represented by Formula (3) is a cyclic group included in the finite field represented by Formula (1). Elements of the torus are represented by two components of the finite field represented by Formula (2). This representation is referred to as affine representation. In this way, when a key and encrypted data of a public key cipher are elements of this torus, the length of the key and the encrypted data can be compressed to ⅓.Fq6  (1)Fq  (2)T6(Fq)  (3)
In the following explanation, the finite field represented by Formula (1) may be written as Fq^6.
However, an exceptional point representing an element that cannot be compressed into the affine representation is present in T6(Fq). The exceptional point cannot be represented the same as the other points. According to Rubin, although encryption fails when an exceptional point appears, because a probability of the appearance of the exceptional point is low, the probability can be neglected. However, in arithmetic operations such as multiplication, square, exponentiation, inverse element, and Frobenius map in the public key cipher, a normal point may be mapped to the exceptional point even if the probability is low. Therefore, the exceptional point is inevitably used as encrypted data and a public key.
If elements of the torus is represented by extension field representation (explained in detail later) or projective representation (explained in detail later), the problem does not occur because the exceptional point can also be represented. However, the effect of compression cannot be obtained because the representation is not the affine representation.